package com.example.question.tree.tree3;

import com.example.question.tree.tree1.Tree;
import com.example.question.tree.tree1.TreeNode;

/**
 * @Date 2023-07-15
 * @Author Jonathan
 */
public class Code12_99 {
    public static void main(String[] args) {
        TreeNode node = Tree.createTree(new Integer[]{3, 1, null, null, 4, 2, null, null, null});
        TreeNode node1 = Tree.createTree(new Integer[]{1, 3, null, 2, null, null});
        Code12_99 code = new Code12_99();
//        code.dfs(node);
//        System.out.println();
        code.dfs(node1);
    }

    private TreeNode prv = new TreeNode(Integer.MIN_VALUE);
    private TreeNode p1, p2, q1, q2;
    private int count = 0;

    public void recoverTree(TreeNode root) {
        dfs(root);
        if (p1 != null && q1 != null) {
            int val = p1.val;
            p1.val = q2.val;
            q2.val = val;
        }
        if (p1 != null && q1 == null) {
            int val = p1.val;
            p1.val = p2.val;
            p2.val = val;

        }
    }


    // 1 3 2 4
    private void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        // 中序遍历
        update(node);
        dfs(node.right);
    }

    // 两个节点要是不相邻的话 直接找到 交换值即可
    // 如果是相邻的两个节点  比较麻烦
    private void update(TreeNode node) {
        if (node.val < prv.val) {
            if (count == 0) {
                p1 = prv;
                p2 = node;
                count++;
            }
            if (count > 0) {
                q1 = prv;
                q2 = node;
            }
        }
        prv = node;
    }
}
